class Solution1 {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length() != s3.length()) return false ;
        s1 = " "+s1 ;
        s2 = " "+s2 ;
        s3 = " "+s3 ;
        int n = s1.length() ;
        int m = s2.length() ;
        int s = s3.length() ;

        boolean[][] dp = new boolean[n][m] ;
        dp[0][0] = true ;
        char[] s1Arr = s1.toCharArray() ;
        char[] s2Arr = s2.toCharArray() ;
        char[] s3Arr = s3.toCharArray() ;
        for(int i=1 ; i<m ; i ++){
            if(s2Arr[i]==s3Arr[i] && dp[0][i-1] ){
                dp[0][i] = true ;
            }
        }
        for(int i=1 ; i< n; i ++){
            if(s1Arr[i]==s3Arr[i] && dp[i-1][0]){
                dp[i][0] = true ;
            }
        }
        for(int i=1 ; i< n ; i ++){
            for(int j=1 ; j< m ; j ++){
                if(s3Arr[i+j]==s1Arr[i] ){
                    dp[i][j] = dp[i-1][j] ;
                }
                if(s3Arr[i+j]==s2Arr[j]){
                    dp[i][j] = dp[i][j] || dp[i][j-1] ;
                }
            }
        }
        return dp[n-1][m-1];
    }
}